class Solution {
    public static int reversePairs(int[] nums) {
        //若数组为空或数组长度为1,则逆序对数目为0
        if (nums == null || nums.length < 2) return 0;
        return mergeSort2(nums,0,nums.length-1);
    }
    public static int mergeSort2(int[] nums,int left,int right) {
        //若只有一个元素,返回0
        if (left == right) return 0;
        //mid标记中间位置
        int mid = left + ((right-left) >> 1);
        //边排序边统计个数
        return mergeSort2(nums,left,mid)
                + mergeSort2(nums,mid+1,right)
                + merge2(nums,left,mid,right);
    }
    public static int merge2(int[] nums,int left,int mid,int right) {
        //创建辅助数组
        int [] helper = new int[right-left+1];
        //i标记辅助数组当前下标
        int i = 0;
        //p1标记左边区域第一个元素
        int p1 = left;
        //p2标记右边区域第一个元素
        int p2 = mid+1;
        //res记录逆序数
        int res = 0;
        //排序并计数
        while (p1 <= mid && p2 <= right) {
            res += nums[p1] > nums[p2] ? right-p2+1 : 0;
            helper[i++] = nums[p1] > nums[p2] ? nums[p1++] : nums[p2++];
        }
        while (p1 <= mid) helper[i++] = nums[p1++];
        while (p2 <= right) helper[i++] = nums[p2++];
        //将helper数组元素复制给原数组
        for (int j = 0; j < helper.length; j++) {
            nums[left+j] = helper[j];
        }
        return res;
    }
}